S04-04 集合框架-数据结构
[TOC]
本章专题与脉络
数据结构剖析
我们举一个形象的例子来理解数据结构的作用：
**战场：**程序运行所需的软件、硬件环境
**敌人：**项目或模块的功能需求
**指挥官：**编写程序的程序员
**士兵和装备：**一行一行的代码
**战术和策略：**数据结构
没有战术，打仗事倍功半
有战术，打仗事半功倍
总结：简单来说，数据结构，就是一种程序设计优化的方法论，研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，目的是加快程序的执行速度、减少内存占用的空间。
具体研究对象如下：
研究对象一：数据间逻辑关系
数据的逻辑结构指反映数据元素之间的逻辑关系，而与数据的存储无关，是独立于计算机的。
- 集合结构：数据结构中的元素之间除了“
同属一个集合” 的相互关系外，别无其他关系。集合元素之间没有逻辑关系。 - 线性结构：数据结构中的元素存在
一对一的相互关系。比如：排队。结构中必须存在唯一的首元素和唯一的尾元素。体现为：一维数组、链表、栈、队列 - 树形结构：数据结构中的元素存在
一对多的相互关系。比如：家谱、文件系统、组织架构 - 图形结构：数据结构中的元素存在
多对多的相互关系。比如：全国铁路网、地铁图
研究对象二：数据的存储结构（或物理结构）
数据的物理结构/存储结构：包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。
结构1：顺序结构
顺序结构就是使用一组连续的存储单元依次存储逻辑上相邻的各个元素。
优点： 只需要申请存放数据本身的内存空间即可，支持下标访问，也可以实现随机访问。
缺点： 必须静态分配连续空间，内存空间的利用率比较低。插入或删除可能需要移动大量元素，效率比较低
结构2：链式结构
- 不使用连续的存储空间存放结构的元素，而是为每一个元素构造一个节点。节点中除了存放数据本身以外，还需要存放指向下一个节点的指针。
- 优点：不采用连续的存储空间导致内存空间利用率比较高，克服顺序存储结构中预知元素个数的缺点。插入或删除元素时，不需要移动大量的元素。
- 缺点：需要额外的空间来表达数据之间的逻辑关系，不支持下标访问和随机访问。
结构3：索引结构
- 除建立存储节点信息外，还建立附加的
索引表来记录每个元素节点的地址。索引表由若干索引项组成。索引项的一般形式是：（关键字，地址）。 - 优点：用节点的索引号来确定结点存储地址，检索速度快。
- 缺点： 增加了附加的索引表，会占用较多的存储空间。在增加和删除数据时要修改索引表，因而会花费较多的时间。
结构4：散列结构
- 根据元素的关键字直接计算出该元素的存储地址，又称为Hash存储。
- 优点：检索、增加和删除结点的操作都很快。
- 缺点：不支持排序，一般比用线性表存储需要更多的空间，并且记录的关键字不能重复。
研究对象三：运算结构
施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。
- 分配资源，建立结构，释放资源
- 插入和删除
- 获取和遍历
- 修改和排序
小结
一维数组
数组的特点
- 在Java中，数组是用来存放同一种数据类型的集合，注意只能存放同一种数据类型。
java
//只声明了类型和长度
数据类型[] 数组名称 = new 数据类型[数组长度];
//声明了类型，初始化赋值，大小由元素个数决定
数据类型[] 数组名称 = {数组元素1，数组元素2，......}例如：整型数组
例如：对象数组
- 物理结构特点：
- 申请内存：一次申请一大段连续的空间，一旦申请到了，内存就固定了。
- 不能动态扩展(初始化给大了，浪费；给小了，不够用)，插入快，删除和查找慢。
- 存储特点：所有数据存储在这个连续的空间中，数组中的每一个元素都是一个具体的数据（或对象），所有数据都紧密排布，不能有间隔。
- 具体的，如下图：
自定义数组
java
package com.atguigu01.overview.array;
/**
* @author 尚硅谷-宋红康
* @create 14:39
*/
class Array {
private Object[] elementData;
private int size;
public Array(int capacity){
elementData = new Object[capacity];
}
/**
* 添加元素
* @param value
*/
public void add(Object value){
if(size >= elementData.length){
throw new RuntimeException("数组已满，不可添加");
}
elementData[size] = value;
size++;
}
/**
* 查询元素value在数组中的索引位置
* @param value
* @return
*/
public int find(Object value){
for (int i = 0; i < size; i++) {
if(elementData[i].equals(value)){
return i;
}
}
return -1;
}
/**
* 从当前数组中移除首次出现的value元素
* @param value
* @return
*/
public boolean delete(Object value){
int index = find(value);
if(index == -1){
return false;
}
for(int i = index;i < size - 1;i++){
elementData[i] = elementData[i + 1];
}
elementData[size - 1] = null;
size--;
return true;
}
/**
* 将数组中首次出现的oldValue替换为newValue
* @param oldValue
* @param newValue
* @return
*/
public boolean update(Object oldValue,Object newValue){
int index = find(oldValue);
if(index == -1){
return false;
}
elementData[index] = newValue;
return true;
}
/**
* 遍历数组中所有数据
*/
public void print(){
System.out.print("{");
for (int i = 0; i < size; i++) {
if(i == size - 1){
System.out.println(elementData[i] + "}");
break;
}
System.out.print(elementData[i] + ",");
}
}
}
//测试类
public class ArrayTest {
public static void main(String[] args) {
Array arr = new Array(10);
arr.add(123);
arr.add("AA");
arr.add(345);
arr.add(345);
arr.add("BB");
arr.delete(345);
arr.update(345,444);
arr.print();
}
}链表
链表的特点
逻辑结构：线性结构
物理结构：不要求连续的存储空间
存储特点：链表由一系列结点node（链表中每一个元素称为结点）组成，结点可以在代码执行过程中动态创建。每个结点包括两个部分：一个是存储数据元素的
数据域，另一个是存储下一个结点地址的指针域。
- 常见的链表结构有如下的形式：
自定义链表
自定义单向链表
java
/*
单链表中的节点。
节点是单向链表中基本的单元。
每一个节点Node都有两个属性：
一个属性：是存储的数据。
另一个属性：是下一个节点的内存地址。
*/
public class Node {
// 存储的数据
Object data;
// 下一个节点的内存地址
Node next;
public Node(){
}
public Node(Object data, Node next){
this.data = data;
this.next = next;
}
}java
/*
链表类(单向链表)
*/
public class Link<E> {
// 头节点
Node header;
private int size = 0;
public int size(){
return size;
}
// 向链表中添加元素的方法（向末尾添加）
//public void add(Object data){
public void add(E data){
// 创建一个新的节点对象
// 让之前单链表的末尾节点next指向新节点对象。
// 有可能这个元素是第一个，也可能是第二个，也可能是第三个。
if(header == null){
// 说明还没有节点。
// new一个新的节点对象，作为头节点对象。
// 这个时候的头节点既是一个头节点，又是一个末尾节点。
header = new Node(data, null);
}else {
// 说明头不是空！
// 头节点已经存在了！
// 找出当前末尾节点，让当前末尾节点的next是新节点。
Node currentLastNode = findLast(header);
currentLastNode.next = new Node(data, null);
}
size++;
}
/**
* 专门查找末尾节点的方法。
*/
private Node findLast(Node node) {
if(node.next == null) {
// 如果一个节点的next是null
// 说明这个节点就是末尾节点。
return node;
}
// 程序能够到这里说明：node不是末尾节点。
return findLast(node.next); // 递归算法！
}
/*// 删除链表中某个数据的方法
public void remove(Object obj){
//略
}
// 修改链表中某个数据的方法
public void modify(Object newObj){
//略
}
// 查找链表中某个元素的方法。
public int find(Object obj){
//略
}*/
}自定义双向链表
Node 类
java/** 双向链表中的节点类 Node */ public class Node<E> { Node prev; // 指向前一个节点 E data; // 数据 Node next; // 指向下一个节点 Node(Node prev, E data, Node next) { this.prev = prev; this.data = data; this.next = next; } }双向链表 MyLinkedList
java/** 双向链表类 MyLinkedList */ public class MyLinkedList<E> implements Iterable<E>{ private Node first; //链表的首元素 private Node last; //链表的尾元素 private int total; //链表的长度 public void add(E e){...} // 添加节点 public int size(){...} // 链表长度 public void delete(Object obj){...} // 移除节点 private Node findNode(Object obj){...} // 查找节点 public boolean contains(Object obj){...} // 是否包含某节点 public void update(E old, E value){...} // 更新节点 @Override public Iterator<E> iterator() {... } /// 迭代器 }添加节点
add(E e)javapublic void add(E e){ Node newNode = new Node(last, e, null); if(first == null){ first = newNode; }else{ last.next = newNode; } last = newNode; total++; }链表长度
size()javapublic int size(){ return total; }移除节点
delete(Object obj)javapublic void delete(Object obj){ Node find = findNode(obj); if(find != null){ if(find.prev != null){ find.prev.next = find.next; }else{ first = find.next; } if(find.next != null){ find.next.prev = find.prev; }else{ last = find.prev; } find.prev = null; find.next = null; find.data = null; total--; } }查找节点
findNode(Object obj)javaprivate Node findNode(Object obj){ Node node = first; Node find = null; if(obj == null){ while(node != null){ if(node.data == null){ find = node; break; } node = node.next; } }else{ while(node != null){ if(obj.equals(node.data)){ find = node; break; } node = node.next; } } return find; }是否包含某节点
contains(Object obj)javapublic boolean contains(Object obj){ return findNode(obj) != null; }更新节点
update(E old, E value)javapublic void update(E old, E value){ Node find = findNode(old); if(find != null){ find.data = value; } }迭代器
iterator()java@Override public Iterator<E> iterator() { return new Itr(); } private class Itr implements Iterator<E>{ private Node<E> node = first; @Override public boolean hasNext() { return node!=null; } @Override public E next() { E value = node.data; node = node.next; return value; } }
测试：
javapackage com.atguigu.list; public class MyLinkedListTest { public static void main(String[] args) { MyLinkedList<String> my = new MyLinkedList<>(); my.add("hello"); my.add("world"); my.add(null); my.add(null); my.add("java"); my.add("java"); my.add("atguigu"); System.out.println("一共有：" + my.size()); System.out.println("所有元素："); for (String s : my) { System.out.println(s); } System.out.println("-------------------------------------"); System.out.println("查找java,null,haha的结果："); System.out.println(my.contains("java")); System.out.println(my.contains(null)); System.out.println(my.contains("haha")); System.out.println("-------------------------------------"); System.out.println("替换java,null后："); my.update("java","JAVA"); my.update(null,"songhk"); System.out.println("所有元素："); for (String s : my) { System.out.println(s); } System.out.println("-------------------------------------"); System.out.println("删除hello，JAVA,null，atguigu后："); my.delete("hello"); my.delete("JAVA"); my.delete(null); my.delete("atguigu"); System.out.println("所有元素："); for (String s : my) { System.out.println(s); } } }
栈
栈的特点
栈（Stack）又称为堆栈或堆叠，是限制仅在表的一端进行插入和删除运算的线性表。
栈按照
先进后出(FILO,first in last out)的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶。每次删除（退栈）的总是删除当前栈中最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。核心类库中的栈结构有Stack和LinkedList。
- Stack就是顺序栈，它是Vector的子类。
- LinkedList是链式栈。
体现栈结构的操作方法：
- peek()方法：查看栈顶元素，不弹出
- pop()方法：弹出栈
- push(E e)方法：压入栈
时间复杂度:
- 索引:
O(n) - 搜索:
O(n) - 插入:
O(1) - 移除:
O(1)
- 索引:
图示：
Stack使用举例
java
/**
* @author 尚硅谷-宋红康
* @create 15:44
*/
public class TestStack {
/*
* 测试Stack
* */
@Test
public void test1(){
Stack<Integer> list = new Stack<>();
list.push(1);
list.push(2);
list.push(3);
System.out.println("list = " + list);
System.out.println("list.peek()=" + list.peek());
System.out.println("list.peek()=" + list.peek());
System.out.println("list.peek()=" + list.peek());
/*
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());//java.util.NoSuchElementException
*/
while(!list.empty()){
System.out.println("list.pop() =" + list.pop());
}
}
/*
* 测试LinkedList
* */
@Test
public void test2(){
LinkedList<Integer> list = new LinkedList<>();
list.push(1);
list.push(2);
list.push(3);
System.out.println("list = " + list);
System.out.println("list.peek()=" + list.peek());
System.out.println("list.peek()=" + list.peek());
System.out.println("list.peek()=" + list.peek());
/*
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());//java.util.NoSuchElementException
*/
while(!list.isEmpty()){
System.out.println("list.pop() =" + list.pop());
}
}
}自定义栈
java
public class MyStack {
// 向栈当中存储元素，我们这里使用一维数组模拟。存到栈中，就表示存储到数组中。
// 为什么选择Object类型数组？因为这个栈可以存储java中的任何引用类型的数据
private Object[] elements;
// 栈帧，永远指向栈顶部元素
// 那么这个默认初始值应该是多少。注意：最初的栈是空的，一个元素都没有。
//private int index = 0; // 如果index采用0，表示栈帧指向了顶部元素的上方。
//private int index = -1; // 如果index采用-1，表示栈帧指向了顶部元素。
private int index;
/**
* 无参数构造方法。默认初始化栈容量10.
*/
public MyStack() {
// 一维数组动态初始化
// 默认初始化容量是10.
this.elements = new Object[10];
// 给index初始化
this.index = -1;
}
/**
* 压栈的方法
* @param obj 被压入的元素
*/
public void push(Object obj) throws Exception {
if(index >= elements.length - 1){
//方式1：
//System.out.println("压栈失败，栈已满！");
//return;
//方式2：
throw new Exception("压栈失败，栈已满！");
}
// 程序能够走到这里，说明栈没满
// 向栈中加1个元素，栈帧向上移动一个位置。
index++;
elements[index] = obj;
System.out.println("压栈" + obj + "元素成功，栈帧指向" + index);
}
/**
* 弹栈的方法，从数组中往外取元素。每取出一个元素，栈帧向下移动一位。
* @return
*/
public Object pop() throws Exception {
if (index < 0) {
//方式1：
//System.out.println("弹栈失败，栈已空！");
//return;
//方式2：
throw new Exception("弹栈失败，栈已空！");
}
// 程序能够执行到此处说明栈没有空。
Object obj = elements[index];
System.out.print("弹栈" + obj + "元素成功，");
elements[index] = null;
// 栈帧向下移动一位。
index--;
return obj;
}
// set和get也许用不上，但是你必须写上，这是规矩。你使用IDEA生成就行了。
// 封装：第一步：属性私有化，第二步：对外提供set和get方法。
public Object[] getElements() {
return elements;
}
public void setElements(Object[] elements) {
this.elements = elements;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
}队列
队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。
队列是逻辑结构，其物理结构可以是数组，也可以是链表。
队列的修改原则：队列的修改是依
先进先出（FIFO）的原则进行的。新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。图示：
树与二叉树
树的理解
专有名词解释：
结点：树中的数据元素都称之为结点
根节点：最上面的结点称之为根，一颗树只有一个根且由根发展而来，从另外一个角度来说，每个结点都可以认为是其子树的根
父节点：结点的上层结点，如图中，结点K的父节点是E、结点L的父节点是G
子节点：节点的下层结点，如图中，节点E的子节点是K节点、节点G的子节点是L节点
兄弟节点：具有相同父节点的结点称为兄弟节点，图中F、G、H互为兄弟节点
结点的度数：每个结点所拥有的子树的个数称之为结点的度，如结点B的度为3
树叶：度数为0的结点，也叫作终端结点，图中D、K、F、L、H、I、J都是树叶
非终端节点（或分支节点）：树叶以外的节点，或度数不为0的节点。图中根、A、B、C、E、G都是
树的深度（或高度）：树中结点的最大层次数，图中树的深度为4
结点的层数：从根节点到树中某结点所经路径上的分支树称为该结点的层数，根节点的层数规定为1，其余结点的层数等于其父亲结点的层数+1
同代：在同一棵树中具有相同层数的节点
二叉树的基本概念
二叉树（Binary tree）是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。许多实际问题抽象出来的数据结构往往是二叉树形式，二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。
二叉树的遍历
前序遍历：中左右（根左右）
即先访问根结点，再前序遍历左子树，最后再前序遍历右子 树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。
中序遍历：左中右（左根右）
即先中前序遍历左子树，然后再访问根结点，最后再中序遍 历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。
后序遍历：左右中（左右根）
即先后序遍历左子树，然后再后序遍历右子树，最后访问根 结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。
前序遍历：ABDHIECFG
中序遍历：HDIBEAFCG
后序遍历：HIDEBFGCA
经典二叉树
1、满二叉树： 除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。 第n层的结点数是2的n-1次方，总的结点个数是2的n次方-1
2、完全二叉树： 叶结点只能出现在最底层的两层，且最底层叶结点均处于次底层叶结点的左侧。
3、二叉排序/查找/搜索树：即为BST (binary search/sort tree)。满足如下性质： （1）若它的左子树不为空，则左子树上所有结点的值均小于它的根节点的值； （2）若它的右子树上所有结点的值均大于它的根节点的值； （3）它的左、右子树也分别为二叉排序/查找/搜索树。
对二叉查找树进行中序遍历，得到有序集合。便于检索。
4、平衡二叉树：（Self-balancing binary search tree）首先是二叉排序树，此外具有以下性质： （1）它是一棵空树或它的左右两个子树的高度差的绝对值不超过1 （2）并且左右两个子树也都是一棵平衡二叉树 （3）不要求非叶节点都有两个子结点
平衡二叉树的目的是为了减少二叉查找树的层次，提高查找速度。平衡二叉树的常用实现有红黑树、AVL、替罪羊树、Treap、伸展树等。
6、红黑树：即Red-Black Tree。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，它是在 1972 年由 Rudolf Bayer 发明的。红黑树是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在 O(log n)时间内做查找，插入和删除， 这里的 n 是树中元素的数目。
红黑树的特性：
每个节点是红色或者黑色
根节点是黑色
每个叶子节点（NIL）是黑色。（注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点）
每个红色节点的两个子节点都是黑色的。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（确保没有一条路径会比其他路径长出2倍）
当我们插入或删除节点时，可能会破坏已有的红黑树，使得它不满足以上5个要求，那么此时就需要进行处理，使得它继续满足以上的5个要求：
1、recolor ：将某个节点变红或变黑
2、rotation ：将红黑树某些结点分支进行旋转（左旋或右旋）
红黑树可以通过红色节点和黑色节点尽可能的保证二叉树的平衡。主要是用它来存储有序的数据，它的时间复杂度是O(logN)，效率非常之高。
二叉树及其结点的表示
普通二叉树：
java
public class BinaryTree<E>{
private TreeNode root; //二叉树的根结点
private int total;//结点总个数
private class TreeNode{
//至少有以下几个部分
TreeNode parent;
TreeNode left;
E data;
TreeNode right;
public TreeNode(TreeNode parent, TreeNode left, E data, TreeNode right) {
this.parent = parent;
this.left = left;
this.data = data;
this.right = right;
}
}
}TreeMap红黑树：
java
public class TreeMap<K,V> {
private transient Entry<K,V> root;
private transient int size = 0;
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
}List接口分析
List接口特点
- List集合所有的元素是以一种
线性方式进行存储的，例如，存元素的顺序是11、22、33。那么集合中，元素的存储就是按照11、22、33的顺序完成的）。 - 它是一个元素
存取有序的集合。即元素的存入顺序和取出顺序有保证。 - 它是一个
带有索引的集合，通过索引就可以精确的操作集合中的元素（与数组的索引是一个道理）。 - 集合中可以有
重复的元素，通过元素的equals方法，来比较是否为重复的元素。
注意：
List集合关心元素是否有序，而不关心是否重复，请大家记住这个原则。例如“张三”可以领取两个号。
- List接口的主要实现类
- ArrayList：动态数组
- Vector：动态数组
- LinkedList：双向链表
- Stack：栈
动态数组ArrayList与Vector
Java的List接口的实现类中有两个动态数组的实现：ArrayList 和 Vector。
ArrayList与Vector的区别
它们的底层物理结构都是数组，我们称为动态数组。
- ArrayList是新版的动态数组，线程不安全，效率高，Vector是旧版的动态数组，线程安全，效率低。
- 动态数组的扩容机制不同，ArrayList默认扩容为原来的1.5倍，Vector默认扩容增加为原来的2倍。
- 数组的初始化容量，如果在构建ArrayList与Vector的集合对象时，没有显式指定初始化容量，那么Vector的内部数组的初始容量默认为10，而ArrayList在JDK 6.0 及之前的版本也是10，JDK8.0 之后的版本ArrayList初始化为长度为0的空数组，之后在添加第一个元素时，再创建长度为10的数组。原因：
- 用的时候，再创建数组，避免浪费。因为很多方法的返回值是ArrayList类型，需要返回一个ArrayList的对象，例如：后期从数据库查询对象的方法，返回值很多就是ArrayList。有可能你要查询的数据不存在，要么返回null，要么返回一个没有元素的ArrayList对象。
ArrayList部分源码分析
JDK1.7.0_07中：
java
//属性
private transient Object[] elementData; //存储底层数组元素
private int size; //记录数组中存储的元素的个数
//构造器
public ArrayList() {
this(10); //指定初始容量为10
}
public ArrayList(int initialCapacity) {
super();
//检查初始容量的合法性
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
//数组初始化为长度为initialCapacity的数组
this.elementData = new Object[initialCapacity];
}
//方法：add()相关方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); //查看当前数组是否够多存一个元素
elementData[size++] = e; //将元素e添加到elementData数组中
return true;
}
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// 如果if条件满足，则进行数组的扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; //当前数组容量
int newCapacity = oldCapacity + (oldCapacity >> 1); //新数组容量是旧数组容量的1.5倍
if (newCapacity - minCapacity < 0) //判断旧数组的1.5倍是否够
newCapacity = minCapacity;
//判断旧数组的1.5倍是否超过最大数组限制
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//复制一个新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
//方法：remove()相关方法
public E remove(int index) {
rangeCheck(index); //判断index是否在有效的范围内
modCount++; //修改次数加1
//取出[index]位置的元素，[index]位置的元素就是要被删除的元素，用于最后返回被删除的元素
E oldValue = elementData(index);
int numMoved = size - index - 1; //确定要移动的次数
//如果需要移动元素，就用System.arraycopy移动元素
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
//将elementData[size-1]位置置空，让GC回收空间，元素个数减少
elementData[--size] = null;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size) //index不合法的情况
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) { //返回指定位置的元素
return (E) elementData[index];
}
//方法：set()方法相关
public E set(int index, E element) {
rangeCheck(index); //检验index是否合法
//取出[index]位置的元素，[index]位置的元素就是要被替换的元素，用于最后返回被替换的元素
E oldValue = elementData(index);
//用element替换[index]位置的元素
elementData[index] = element;
return oldValue;
}
//方法：get()相关方法
public E get(int index) {
rangeCheck(index); //检验index是否合法
return elementData(index); //返回[index]位置的元素
}
//方法：indexOf()
public int indexOf(Object o) {
//分为o是否为空两种情况
if (o == null) {
//从前往后找
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//方法：lastIndexOf()
public int lastIndexOf(Object o) {
//分为o是否为空两种情况
if (o == null) {
//从后往前找
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}jdk1.8.0_271中：
java
//属性
transient Object[] elementData;
private int size;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//构造器
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //初始化为空数组
}
//方法:add()相关方法
public boolean add(E e) {
//查看当前数组是否够多存一个元素
ensureCapacityInternal(size + 1); // Increments modCount!!
//存入新元素到[size]位置，然后size自增1
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果当前数组还是空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//那么minCapacity取DEFAULT_CAPACITY与minCapacity的最大值
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//查看是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //修改次数加1
//如果需要的最小容量比当前数组的长度大，即当前数组不够存，就扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; //当前数组容量
int newCapacity = oldCapacity + (oldCapacity >> 1); //新数组容量是旧数组容量的1.5倍
//看旧数组的1.5倍是否够
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//看旧数组的1.5倍是否超过最大数组限制
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//复制一个新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}ArrayList相关方法图示
- ArrayList采用数组作为底层实现
- ArrayList自动扩容过程
- ArrayList的add(E e)方法
- ArrayList的add(int index,E e)方法
Vector部分源码分析
jdk1.8.0_271中：
测试代码
无参构造方法
Vector()java//属性 protected Object[] elementData; protected int elementCount; //构造器 public Vector() { this(10); //指定初始容量initialCapacity为10 }有参构造方法
Vector(10)javapublic Vector(int initialCapacity) { // (10) this(initialCapacity, 0); //指定capacityIncrement增量为0 }0有参构造方法
Vector(10, 0)javapublic Vector(int initialCapacity, int capacityIncrement) { // (10, 0) super(); //1. 判断了形参初始容量initialCapacity的合法性 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); //2. 创建了一个Object[]类型的数组 this.elementData = new Object[initialCapacity]; //3. 增量，默认是0，如果是0，后面就按照2倍增加，如果不是0，后面就按照你指定的增量进行增量 this.capacityIncrement = capacityIncrement; }
添加元素方法
vector.add(i)javapublic synchronized boolean add(E e) { //synchronized意味着线程安全的 // 1. 更新修改次数 modCount++; // 3. 看是否需要扩容 ensureCapacityHelper(elementCount + 1); // (i+1) // 2. 把新的元素存入[elementCount]，存入后，elementCount元素的个数增1 elementData[elementCount++] = e; return true; }查看是否需要扩容
ensureCapacityHelper(i + 1)javaprivate void ensureCapacityHelper(int minCapacity) { // (i+1) //看是否超过了当前数组的容量 if (minCapacity - elementData.length > 0) // (i+1, 10) grow(minCapacity); //扩容 }条件
minCapacity - elementData.length > 0满足时，执行扩容方法grow(11)javaprivate void grow(int minCapacity) { // (11) // 1. 保存旧容量，并计算新容量 int oldCapacity = elementData.length; //获取目前数组的长度 //如果capacityIncrement增量是0，新容量 = oldCapacity的2倍 //如果capacityIncrement增量是不是0，新容量 = oldCapacity + capacityIncrement增量; int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); // 2. 判断边缘条件 // 2.1 如果按照上面计算的新容量还不够，就按照你指定的需要的最小容量来扩容minCapacity if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 2.2 如果新容量超过了最大数组限制，那么单独处理 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 3. 把旧数组中的数据复制到新数组中，新数组的长度为newCapacity elementData = Arrays.copyOf(elementData, newCapacity); // (elementData, 20) }
移除元素方法
vector.remove(el)javapublic boolean remove(Object o) { // (el) return removeElement(o); }实际执行移除元素的方法
removeElement(el)javapublic synchronized boolean removeElement(Object obj) { // (el) // 1. 更新修改次数 modCount++; // 2. 查找obj在当前Vector中的下标 int i = indexOf(obj); // 3. 如果i>=0，说明存在，删除[i]位置的元素，返回true表示删除成功 if (i >= 0) { removeElementAt(i); return true; } // 4. 返回false表示删除失败 return false; }
通过索引移除元素方法
vector.removeElementAt(i)javapublic synchronized void removeElementAt(int index) { // (i) // 1. 更新修改次数 modCount++; // 2. 判断下标是否越界 if (index >= elementCount) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } else if (index < 0) { throw new ArrayIndexOutOfBoundsException(index); } // 3. 调用System.arraycopy移动元素 int j = elementCount - index - 1; // j是要移动的元素的个数 if (j > 0) { //把index+1位置以及后面的元素往前移动 //index+1的位置的元素移动到index位置，依次类推 //一共移动j个 System.arraycopy(elementData, index + 1, elementData, index, j); } //元素的总个数减少 elementCount--; //将elementData[elementCount]这个位置置空，用来添加新元素，位置的元素等着被GC回收 elementData[elementCount] = null; /* to let gc do its work */ }查找元素的下标
indexOf(el)javapublic int indexOf(Object o) { // (el) return indexOf(o, 0); // (el, 0) }实际执行查找元素的方法
indexOf(el, 0)javapublic synchronized int indexOf(Object o, int index) { if (o == null) { //如果要查找的元素是null值，用==null判断 for (int i = index ; i < elementCount ; i++) if (elementData[i]==null) return i; } else { //如果要查找的元素是非null值，用equals判断 for (int i = index ; i < elementCount ; i++) if (o.equals(elementData[i])) return i; } return -1; }
链表LinkedList
Java中有双链表的实现：LinkedList，它是List接口的实现类。
LinkedList是一个双向链表，如图所示：
链表与动态数组的区别
动态数组底层的物理结构是数组，因此根据索引访问的效率非常高。但是非末尾位置的插入和删除效率不高，因为涉及到移动元素。另外添加操作时涉及到扩容问题，就会增加时空消耗。
链表底层的物理结构是链表，因此根据索引访问的效率不高，即查找元素慢。但是插入和删除不需要移动元素，只需要修改前后元素的指向关系即可，所以插入、删除元素快。而且链表的添加不会涉及到扩容问题。
LinkedList源码分析
jdk1.8.0_271中：
new LinkedList()
测试：new LinkedList()
java
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(1);
System.out.println("linkedList=" + linkedList);
}new LinkedList()：构造器初始化java//属性 transient Node<E> first; //记录第一个结点的位置 transient Node<E> last; //记录当前链表的尾元素 transient int size = 0; //记录最后一个结点的位置 //构造器 public LinkedList() {}
.add(E e)
测试：.add(el)
java
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
System.out.println("linkedList=" + linkedList);
}.add(1)：添加元素javapublic boolean add(E e) { linkLast(e); //默认把新元素链接到链表尾部 return true; }linkLast(e)：添加元素到链表尾部javavoid linkLast(E e) { // 1. 用 l 记录原来的最后一个结点 final Node<E> l = last; // last: null->newNode // 2. 创建新结点 final Node<E> newNode = new Node<>(l, e, null); // 3. last 指向新节点，现在的新结点是最后一个结点了 last = newNode; // 4. 判断链表是否为空，执行不同逻辑 if (l == null) //如果l==null，说明原来的链表是空的 //那么新结点同时也是第一个结点 first = newNode; else //否则把新结点链接到原来的最后一个结点的next中 l.next = newNode; // 5. 元素个数增加，修改次数增加 size++; modCount++; }
.remove()/removeFirst()
测试：.remove()
java
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
System.out.println("linkedList=" + linkedList); // [1,2,3]
// 删除第一个节点
linkedList.remove();
System.out.println("linkedList=" + linkedList); // [2,3]
}.remove()： 删除第一个节点javapublic E remove() { return removeFirst(); }removeFirst()：删除第一个节点javapublic E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }unlinkFirst()：实际删除第一个节点javaprivate E unlinkFirst(Node<E> f) { // assert f == first && f != null; // 1. 保存第一个节点 final E element = f.item; // 2. 通过修改指针实现删除第一个节点 final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; // 3. 收尾操作，并返回保存的第一个节点 size--; modCount++; return element; }
.get(int index)
测试：.get(int index)
java
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
System.out.println("linkedList=" + linkedList); // [1,2,3]
// 获取第二个节点（索引从0开始）
Node el = linkedList.get(1);
System.out.println("el=" + el); // 2
}.get(1)：获取第二个节点javapublic E get(int index) { checkElementIndex(index); // index >= 0 && index < size // 返回指定索引节点的值 return node(index).item; }
其他
java
//其中，Node类定义如下
private static class Node<E> {
E item; //元素数据
Node<E> next; //下一个结点
Node<E> prev; //前一个结点
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
//方法：插入add()相关方法
public void add(int index, E element) {
checkPositionIndex(index);//检查index范围
if (index == size)//如果index==size，连接到当前链表的尾部
linkLast(element);
else
linkBefore(element, node(index));
}
Node<E> node(int index) {
// assert isElementIndex(index);
/*
index < (size >> 1)采用二分思想，先将index与长度size的一半比较，如果index<size/2，就只从位置0
往后遍历到位置index处，而如果index>size/2，就只从位置size往前遍历到位置index处。这样可以减少一部
分不必要的遍历。
*/
//如果index<size/2，就从前往后找目标结点
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {//否则从后往前找目标结点
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//把新结点插入到[index]位置的结点succ前面
void linkBefore(E e, Node<E> succ) {//succ是[index]位置对应的结点
// assert succ != null;
final Node<E> pred = succ.prev; //[index]位置的前一个结点
//新结点的prev是原来[index]位置的前一个结点
//新结点的next是原来[index]位置的结点
final Node<E> newNode = new Node<>(pred, e, succ);
//[index]位置对应的结点的prev指向新结点
succ.prev = newNode;
//如果原来[index]位置对应的结点是第一个结点，那么现在新结点是第一个结点
if (pred == null)
first = newNode;
else
pred.next = newNode;//原来[index]位置的前一个结点的next指向新结点
size++;
modCount++;
}
//方法：remove()相关方法
public boolean remove(Object o) {
//分o是否为空两种情况
if (o == null) {
//找到o对应的结点x
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);//删除x结点
return true;
}
}
} else {
//找到o对应的结点x
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);//删除x结点
return true;
}
}
}
return false;
}
E unlink(Node<E> x) {//x是要被删除的结点
// assert x != null;
final E element = x.item;//被删除结点的数据
final Node<E> next = x.next;//被删除结点的下一个结点
final Node<E> prev = x.prev;//被删除结点的上一个结点
//如果被删除结点的前面没有结点，说明被删除结点是第一个结点
if (prev == null) {
//那么被删除结点的下一个结点变为第一个结点
first = next;
} else {//被删除结点不是第一个结点
//被删除结点的上一个结点的next指向被删除结点的下一个结点
prev.next = next;
//断开被删除结点与上一个结点的链接
x.prev = null;//使得GC回收
}
//如果被删除结点的后面没有结点，说明被删除结点是最后一个结点
if (next == null) {
//那么被删除结点的上一个结点变为最后一个结点
last = prev;
} else {//被删除结点不是最后一个结点
//被删除结点的下一个结点的prev执行被删除结点的上一个结点
next.prev = prev;
//断开被删除结点与下一个结点的连接
x.next = null;//使得GC回收
}
//把被删除结点的数据也置空，使得GC回收
x.item = null;
//元素个数减少
size--;
//修改次数增加
modCount++;
//返回被删除结点的数据
return element;
}
public E remove(int index) { //index是要删除元素的索引位置
checkElementIndex(index);
return unlink(node(index));
}LinkedList相关方法图示
- 只有1个元素的LinkedList
- 包含4个元素的LinkedList
- add(E e)方法
- add(int index,E e)方法
- remove(Object obj)方法
- remove(int index)方法
Map接口分析
哈希表的物理结构
HashMap和Hashtable底层都是哈希表（也称散列表），其中维护了一个长度为2的幂次方的Entry类型的数组table，数组的每一个索引位置被称为一个桶(bucket)，你添加的映射关系(key,value)最终都被封装为一个Map.Entry类型的对象，放到某个table[index]桶中。
使用数组的目的是查询和添加的效率高，可以根据索引直接定位到某个table[index]。
HashMap中数据添加过程
JDK7中过程分析
java
// 在底层创建了长度为16的Entry[] table的数组
HashMap map = new HashMap();java
map.put(key1,value1);
/*
分析过程如下：
将(key1,value1)添加到当前hashmap的对象中。首先会调用key1所在类的hashCode()方法，计算key1的哈希值1，
此哈希值1再经过某种运算(hash())，得到哈希值2。此哈希值2再经过某种运算(indexFor())，确定在底层table数组中的索引位置i。
（1）如果数组索引为i上的数据为空，则(key1,value1)直接添加成功 ------位置1
（2）如果数组索引为i上的数据不为空，有(key2,value2)，则需要进一步判断：
判断key1的哈希值2与key2的哈希值是否相同：
（3） 如果哈希值不同，则(key1,value1)直接添加成功 ------位置2
如果哈希值相同，则需要继续调用key1所在类的equals()方法，将key2放入equals()形参进行判断
（4） equals方法返回false : 则(key1,value1)直接添加成功 ------位置3
equals方法返回true : 默认情况下，value1会覆盖value2。
位置1：直接将(key1,value1)以Entry对象的方式存放到table数组索引i的位置。
位置2、位置3：(key1,value1) 与现有的元素以链表的方式存储在table数组索引i的位置，新添加的元素指向旧添加的元素。
...
在不断的添加的情况下，满足如下条件的情况下，会进行扩容:
if ((size >= threshold) && (null != table[bucketIndex])) :
默认情况下，当要添加的元素个数超过12(即：数组的长度 * loadFactor得到的结果)时，就要考虑扩容。
补充：jdk7源码中定义的：
static class Entry<K,V> implements Map.Entry<K,V>
*/java
map.get(key1);
/*
① 计算key1的hash值，用这个方法hash(key1)
② 找index = table.length-1 & hash;
③ 如果table[index]不为空，那么就挨个比较哪个Entry的key与它相同，就返回它的value
*/java
map.remove(key1);
/*
① 计算key1的hash值，用这个方法hash(key1)
② 找index = table.length-1 & hash;
③ 如果table[index]不为空，那么就挨个比较哪个Entry的key与它相同，就删除它，把它前面的Entry的next的值修改为被删除Entry的next
*/JDK8中过程分析
java
/*
①
使用HashMap()的构造器创建对象时，并没有在底层初始化长度为16的table数组。
②
jdk8中添加的key,value封装到了HashMap.Node类的对象中。而非jdk7中的HashMap.Entry。
③
jdk8中新增的元素所在的索引位置如果有其他元素。在经过一系列判断后，如果能添加，则是旧的元素指向新的元素。而非jdk7中的新的元素指向旧的元素。“七上八下”
④
jdk7时底层的数据结构是：数组+单向链表。 而jdk8时，底层的数据结构是：数组+单向链表+红黑树。
红黑树出现的时机：当某个索引位置i上的链表的长度达到8，且数组的长度超过64时，此索引位置上的元素要从单向链表改为红黑树。
如果索引i位置是红黑树的结构，当不断删除元素的情况下，当前索引i位置上的元素的个数低于6时，要从红黑树改为单向链表。
*/HashMap源码剖析
JDK1.7.0_07中源码
Entry
key-value被封装为HashMap.Entry类型，而这个类型实现了Map.Entry接口。
java
public class HashMap<K,V>{
transient Entry<K,V>[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
//略
}
}属性
java
//table数组的默认初始化长度
static final int DEFAULT_INITIAL_CAPACITY = 16;
//哈希表
transient Entry<K,V>[] table;
//哈希表中key-value的个数
transient int size;
//临界值、阈值（扩容的临界值）
int threshold;
//加载因子
final float loadFactor;
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;构造器
java
public HashMap() {
//DEFAULT_INITIAL_CAPACITY：默认初始容量16
//DEFAULT_LOAD_FACTOR：默认加载因子0.75
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}java
public HashMap(int initialCapacity, float loadFactor) {
//校验initialCapacity合法性
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
//校验initialCapacity合法性
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//校验loadFactor合法性
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
//计算得到table数组的长度（保证capacity是2的整次幂）
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
//加载因子，初始化为0.75
this.loadFactor = loadFactor;
// threshold 初始为默认容量
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//初始化table数组
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}put()
java
public V put(K key, V value) {
//如果key是null，单独处理，存储到table[0]中，如果有另一个key为null，value覆盖
if (key == null)
return putForNullKey(value);
//对key的hashCode进行干扰，算出一个hash值
/*
hashCode值 xxxxxxxxxx
table.length-1 000001111
hashCode值 xxxxxxxxxx 无符号右移几位和原来的hashCode值做^运算，使得hashCode高位二进制值参与计算，
也发挥作用，降低index冲突的概率。
*/
int hash = hash(key);
//计算新的映射关系应该存到table[i]位置，
//i = hash & table.length-1，可以保证i在[0,table.length-1]范围内
int i = indexFor(hash, table.length);
//检查table[i]下面有没有key与我新的映射关系的key重复，如果重复替换value
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//添加新的映射关系
addEntry(hash, key, value, i);
return null;
}其中，
java
//如果key是null，直接存入[0]的位置
private V putForNullKey(V value) {
//判断是否有重复的key，如果有重复的，就替换value
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//把新的映射关系存入[0]的位置，而且key的hash值用0表示
addEntry(0, null, value, 0);
return null;
}java
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}java
static int indexFor(int h, int length) {
return h & (length-1);
}java
void addEntry(int hash, K key, V value, int bucketIndex) {
//判断是否需要库容
//扩容：（1）size达到阈值（2）table[i]正好非空
if ((size >= threshold) && (null != table[bucketIndex])) {
//table扩容为原来的2倍，并且扩容后，会重新调整所有key-value的存储位置
resize(2 * table.length);
//新的key-value的hash和index也会重新计算
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//存入table中
createEntry(hash, key, value, bucketIndex);
}java
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
//原来table[i]下面的映射关系作为新的映射关系next
table[bucketIndex] = new Entry<>(hash, key, value, e);
//个数增加
size++;
}JDK1.8.0_271中源码
Node
key-value被封装为HashMap.Node类型或HashMap.TreeNode类型，它俩都直接或间接的实现了Map.Entry接口。
存储到table数组的可能是Node结点对象，也可能是TreeNode结点对象，它们也是Map.Entry接口的实现类。即table[index]下的映射关系可能串起来一个链表或一棵红黑树。
java
public class HashMap<K,V>{
transient Node<K,V>[] table;
//Node类
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
// 其它结构：略
}
//TreeNode类
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
boolean red; //是红结点还是黑结点
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
//....
}属性
java
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的初始容量 16
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量 1 << 30
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认加载因子
static final int TREEIFY_THRESHOLD = 8; //默认树化阈值8，当链表的长度达到这个值后，要考虑树化
static final int UNTREEIFY_THRESHOLD = 6;//默认反树化阈值6，当树中结点的个数达到此阈值后，要考虑变为链表
//当单个的链表的结点个数达到8，并且table的长度达到64，才会树化。
//当单个的链表的结点个数达到8，但是table的长度未达到64，会先扩容
static final int MIN_TREEIFY_CAPACITY = 64; //最小树化容量64
transient Node<K,V>[] table; //数组
transient int size; //记录有效映射关系的对数，也是Entry对象的个数
int threshold; //阈值，当size达到阈值时，考虑扩容
final float loadFactor; //加载因子，影响扩容的频率put()
测试代码：
java
HashMap<Object, Object> map = new HashMap<>();
map.put("java", 10);
map.put("php", 10);
map.put("java", 20);
System.out.println("map = " + map);构造方法：初始化默认加载因子
javapublic HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75 all other fields defaulted (其他字段都是默认值) }put("java")：添加java元素javapublic V put(K key, V value) { // ("java", 10) return putVal(hash(key), key, value, false, true); }hash(key)：计算key（"java"） 的hash值javastatic final int hash(Object key) { int h; //如果key是null，hash是0 //如果key非null，用key的hashCode值 与 key的hashCode值高16进行异或 // 即就是用key的hashCode值高16位与低16位进行了异或的干扰运算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }如果用key的原始的hashCode值 与 table.length-1 进行按位与（
index = hash & table.length-1），那么基本上高16没机会用上。 这样就会增加冲突的概率，为了降低冲突的概率，把高16位加入到hash信息中。putVal(hash, key, value, onlyIfAbsent, evict)javafinal V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { Node<K,V>[] tab; // 数组 Node<K,V> p; // 一个结点 int n, i; // 数组的长度和下标 /** 1. 初始化与延迟扩容 HashMap 采用延迟加载（Lazy Initialization）策略。在 new HashMap() 时并不会直接分配数组空间。 当首次调用 putVal 时，通过判断 table 是否为 null 或长度为 0，触发 resize() 方法进行实质性的数组初始化。 */ if ((tab = table) == null || (n = tab.length) == 0){ n = (tab = resize()).length; } /** 2. 寻址与空桶直接插入 (n - 1) & hash 是计算元素在数组中索引的高效位运算。 由于数组长度 n 始终为 2 的幂次，(n - 1) 的二进制低位全为 1，进行与运算等价于对 n 取模（hash % n），但执行效率更高。 */ if ((p = tab[i = (n - 1) & hash]) == null){ // 2.1 若定位出的桶位 tab[i] 为 null，直接创建新节点 Node 放入该槽位。 tab[i] = newNode(hash, key, value, null); }else { // 2.2 若定位出的桶位 tab[i] 不为 null，则进行碰撞处理 /** 3. 碰撞处理（红黑树与链表） */ Node<K,V> e; K k; // 3.1 检查首节点是否完全匹配 // 首先比对桶中第一个节点(p)的 hash 和 key。如果相同，说明找到了对应的键，直接用 e 记录该节点。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 3.2 检查是否为红黑树节点 // 若首节点是 TreeNode 类型，说明该桶已转化为红黑树结构，调用 putTreeVal 按照红黑树的规则寻找或插入节点。 else if (p instanceof TreeNode){ e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 3.3 链表遍历与尾部插入 }else { for (int binCount = 0; ; ++binCount) { // a. 若遍历到链表末尾（p.next == null），则在尾部链接新节点。 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // b. 此时若 binCount 达到 TREEIFY_THRESHOLD - 1（即连同新节点在内，链表长度达到 9 时），触发 treeifyBin 方法尝试将链表转换为红黑树。 if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } // c. 在遍历过程中，若发现某个节点的 hash 和 key 与待插入的键完全一致，则终止循环，此时 e 指向该已存在的节点，链表向下移动。 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } /** 4. 值覆盖与容量检查 */ // 4.1 存在相同的 Key，执行 Value 覆盖 // 若 e != null，说明目标 key 已存在。根据 onlyIfAbsent 参数决定是否覆盖。若 onlyIfAbsent 为 false（默认情况）或原值为 null，则用新值覆盖旧值，并返回 oldValue。此流程不增加 size，不改变 modCount。 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); //什么也没干 return oldValue; } } // 4.2 插入新节点后的结构性调整 // 若成功插入了全新节点，并发修改计数器 modCount 自增。当前存储元素总数 size 自增，若自增后的 size 超过了扩容阈值 threshold（capacity * loadFactor），则调用 resize() 进行 2 倍容量的扩容。 ++modCount; if (++size > threshold) resize(); // 一旦扩容，重新调整所有映射关系的位置 afterNodeInsertion(evict); // 什么也没干 return null; }resize()：动态扩容与初始化javafinal Node<K,V>[] resize() { /** 1. 计算新容量与新阈值 */ Node<K,V>[] oldTab = table; // 旧表 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 旧容量 int oldThr = threshold;// 旧阈值（0） int newCap, newThr = 0; // 新容量，新阈值 // 1.1 如果 oldCap > 0，说明哈希表已初始化，数组不再为 null if (oldCap > 0) { // a 超过最大容量限制，不再扩容，并返回旧表 if (oldCap >= MAXIMUM_CAPACITY) { // 2^30 threshold = Integer.MAX_VALUE; return oldTab; } // b 容量翻倍。若原容量大于等于默认初始容量(16)，则阈值也同步翻倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)// 16 newThr = oldThr << 1; // 阈值翻倍 } // 1.2 对应带参构造函数：初始容量暂存在 threshold 中，直接将其赋给 newCap else if (oldThr > 0) newCap = oldThr; // 1.3 对应无参构造函数：完全使用默认值（16和12） else { newCap = DEFAULT_INITIAL_CAPACITY; // 16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 0.75 * 16 = 12 } // 1.4 针对 1.2 的情况修正计算新阈值 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; // 阈值赋值为新阈值 /** 2. 创建新数组并执行数据迁移 */ @SuppressWarnings({"rawtypes","unchecked"}) // 2.1 创建长度为 newCap 的新数组 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { // 2.2 遍历 oldTab 迁移元素到 newTab for (int j = 0; j < oldCap; ++j) { Node<K,V> e; // 数组元素 // 将旧表中的元素赋值给 e 后删除该元素 if ((e = oldTab[j]) != null) { oldTab[j] = null; // 情况一：桶中只有一个孤立节点，直接寻址放入新表 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; // 等价于：e.hash % newCap // 情况二：红黑树节点，调用树拆分逻辑 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 拆解原树，放入新表 // 情况三：普通链表，维护高低位两个链表，保持原有顺序 // 引入了四部指针：低位头/尾（loHead/loTail）和高位头/尾（hiHead/hiTail）。 // 在 do-while 循环中，依靠 (e.hash & oldCap) == 0 将原长链表有条不紊地拆分为两条独立的子链表。 // 由于采用尾插法组装（loTail.next = e），迁移后子链表内部节点保持了原有的相对顺序，成功规避了 Java 7 采用头插法在并发扩容时引起的死循环（死链）隐患。 else { Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; // 把原来table[i]下面的整个链表，重新挪到了新的table中 do { next = e.next; // a 高低位拆分：利用 hash & oldCap 判定归属低位还是高位 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // b 低位链表放回原索引 j 处 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // c 高位链表放到新索引 j + oldCap 处 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }treeifyBin()：树化前置条件校验与节点类型重构javafinal void treeifyBin(Node<K,V>[] tab, int hash) { /** 1. 树化前置条件校验 如果当前数组为空，或者数组长度 n 小于 64，即便某一条链表长度已经达到了 8，由于整体槽位仍较为拥挤，通过 resize() 扩容使数组容量翻倍，能够极大地几率将这条密集的链表一拆为二（高低位拆分），从而在不构建红黑树的情况下消除冲突。 */ int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // 64 resize(); /** 2. 节点替换与双向链表组装 */ else if ((e = tab[index = (n - 1) & hash]) != null) { // 精确定位当前需要树化的槽位 TreeNode<K,V> hd = null, tl = null; do { // 2.1 将普通的单向链表节点 Node 替换转换为 TreeNode TreeNode<K,V> p = replacementTreeNode(e, null); // 2.2 构建双向链表的头节点 if (tl == null) hd = p; // 2.3 维护前驱与后继指针，连接成双向链表 else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); /** 3. 树顶挂载与真正树化 */ if ((tab[index] = hd) != null) hd.treeify(tab); } }
LinkedHashMap源码剖析
源码
内部定义的Entry如下：
java
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}LinkedHashMap重写了HashMap中的newNode()方法：
java
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}java
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
linkNodeLast(p);
return p;
}图示
Set接口分析
Set集合与Map集合的关系
Set的内部实现其实是一个Map，Set中的元素，存储在HashMap的key中。即HashSet的内部实现是一个HashMap，TreeSet的内部实现是一个TreeMap，LinkedHashSet的内部实现是一个LinkedHashMap。
源码剖析
new HashSet()
测试代码：
java
@Test
void testConstructor() {
HashSet<Object> hashSet = new HashSet<>();
}new HashSet<>()：HashSet 的构造方法javapublic HashSet() { // HashSet 的底层实际是 HashMap map = new HashMap<>(); } public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); } public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); } //这个构造器是给子类LinkedHashSet调用的 HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); }new HashMap<>()：HashMap 的构造方法javapublic HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
add()
测试代码：
java
@Test
void testAdd() {
HashSet<Object> hashSet = new HashSet<>();
hashSet.add("tom");
hashSet.add("jack");
hashSet.add("tom");
}.add("tom")：添加tomjavaprivate transient HashMap<E,Object> map; private static final Object PRESENT = new Object(); public boolean add(E e) { return map.put(e, PRESENT)==null; }map.put(e, PRESENT)：调用 HashMap 的源码
HashSet源码：
java
//add()方法：
//其中，
//iterator()方法：
public Iterator<E> iterator() {
return map.keySet().iterator();
}LinkedHashSet源码：
java
//构造器
public LinkedHashSet() {
super(16, .75f, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);//调用HashSet的某个构造器
}
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);//调用HashSet的某个构造器
}TreeSet源码：
java
public TreeSet() {
this(new TreeMap<E,Object>());
}
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
//其中，
private transient NavigableMap<E,Object> m;
//add()方法：
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
//其中，
private static final Object PRESENT = new Object();【拓展】HashMap的相关问题
、说说你理解的哈希算法
hash算法是一种可以从任何数据中提取出其“指纹”的数据摘要算法，它将任意大小的数据映射到一个固定大小的序列上，这个序列被称为hash code、数据摘要或者指纹。比较出名的hash算法有MD5、SHA。hash是具有唯一性且不可逆的，唯一性是指相同的“对象”产生的hash code永远是一样的。
、Entry中的hash属性为什么不直接使用key的hashCode()返回值呢？
不管是JDK1.7还是JDK1.8中，都不是直接用key的hashCode值直接与table.length-1计算求下标的，而是先对key的hashCode值进行了一个运算，JDK1.7和JDK1.8关于hash()的实现代码不一样，但是不管怎么样都是为了提高hash code值与 (table.length-1)的按位与完的结果，尽量的均匀分布。
JDK1.7：
java
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}JDK1.8：
java
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}虽然算法不同，但是思路都是将hashCode值的高位二进制与低位二进制值进行了异或，然高位二进制参与到index的计算中。
为什么要hashCode值的二进制的高位参与到index计算呢？
因为一个HashMap的table数组一般不会特别大，至少在不断扩容之前，那么table.length-1的大部分高位都是0，直接用hashCode和table.length-1进行&运算的话，就会导致总是只有最低的几位是有效的，那么就算你的hashCode()实现的再好也难以避免发生碰撞，这时让高位参与进来的意义就体现出来了。它对hashcode的低位添加了随机性并且混合了高位的部分特征，显著减少了碰撞冲突的发生。
、HashMap是如何决定某个key-value存在哪个桶的呢？
因为hash值是一个整数，而数组的长度也是一个整数，有两种思路：
①hash 值 % table.length会得到一个[0,table.length-1]范围的值，正好是下标范围，但是用%运算效率没有位运算符&高。
②hash 值 & (table.length-1)，任何数 & (table.length-1)的结果也一定在[0, table.length-1]范围。
JDK1.7：
java
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1); //此处h就是hash
}JDK1.8：
java
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // i = (n - 1) & hash
tab[i] = newNode(hash, key, value, null);
//....省略大量代码
}、为什么要保持table数组一直是2的n次幂呢？
因为如果数组的长度为2的n次幂，那么table.length-1的二进制就是一个高位全是0，低位全是1的数字，这样才能保证每一个下标位置都有机会被用到。
举例1：
java
hashCode值是 ？
table.length是10
table.length-1是9
？ ????????
9 00001001
&_____________
00000000 [0]
00000001 [1]
00001000 [8]
00001001 [9]
一定[0]~[9]举例2：
java
hashCode值是 ？
table.length是16
table.length-1是15
？ ????????
15 00001111
&_____________
00000000 [0]
00000001 [1]
00000010 [2]
00000011 [3]
...
00001111 [15]
范围是[0,15]，一定在[0,table.length-1]范围内、解决[index]冲突问题
虽然从设计hashCode()到上面HashMap的hash()函数，都尽量减少冲突，但是仍然存在两个不同的对象返回的hashCode值相同，或者hashCode值就算不同，通过hash()函数计算后，得到的index也会存在大量的相同，因此key分布完全均匀的情况是不存在的。那么发生碰撞冲突时怎么办？
JDK1.8之间使用：数组+链表的结构。
JDK1.8之后使用：数组+链表/红黑树的结构。
即hash相同或hash&(table.lengt-1)的值相同，那么就存入同一个“桶”table[index]中，使用链表或红黑树连接起来。
、为什么JDK1.8会出现红黑树和链表共存呢？
因为当冲突比较严重时，table[index]下面的链表就会很长，那么会导致查找效率大大降低，而如果此时选用二叉树可以大大提高查询效率。
但是二叉树的结构又过于复杂，占用内存也较多，如果结点个数比较少的时候，那么选择链表反而更简单。所以会出现红黑树和链表共存。
、加载因子的值大小有什么关系？
如果太大，threshold就会很大，那么如果冲突比较严重的话，就会导致table[index]下面的结点个数很多，影响效率。
如果太小，threshold就会很小，那么数组扩容的频率就会提高，数组的使用率也会降低，那么会造成空间的浪费。
、什么时候树化？什么时候反树化？
java
static final int TREEIFY_THRESHOLD = 8;//树化阈值
static final int UNTREEIFY_THRESHOLD = 6;//反树化阈值
static final int MIN_TREEIFY_CAPACITY = 64;//最小树化容量当某table[index]下的链表的结点个数达到8，并且table.length>=64，那么如果新Entry对象还添加到该table[index]中，那么就会将table[index]的链表进行树化。
当某table[index]下的红黑树结点个数少于6个，此时，
- 当继续删除table[index]下的树结点，最后这个根结点的左右结点有null，或根结点的左结点的左结点为null，会反树化
- 当重新添加新的映射关系到map中，导致了map重新扩容了，这个时候如果table[index]下面还是小于等于6的个数，那么会反树化
java
package com.atguigu.map;
public class MyKey{
int num;
public MyKey(int num) {
super();
this.num = num;
}
@Override
public int hashCode() {
if(num<=20){
return 1;
}else{
final int prime = 31;
int result = 1;
result = prime * result + num;
return result;
}
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
MyKey other = (MyKey) obj;
if (num != other.num)
return false;
return true;
}
}java
package com.atguigu.map;
import org.junit.Test;
import java.util.HashMap;
public class TestHashMapMyKey {
@Test
public void test1(){
//这里为了演示的效果，我们造一个特殊的类，这个类的hashCode（）方法返回固定值1
//因为这样就可以造成冲突问题，使得它们都存到table[1]中
HashMap<MyKey, String> map = new HashMap<>();
for (int i = 1; i <= 11; i++) {
map.put(new MyKey(i), "value"+i);//树化演示
}
}
@Test
public void test2(){
HashMap<MyKey, String> map = new HashMap<>();
for (int i = 1; i <= 11; i++) {
map.put(new MyKey(i), "value"+i);
}
for (int i = 1; i <=11; i++) {
map.remove(new MyKey(i));//反树化演示
}
}
@Test
public void test3(){
HashMap<MyKey, String> map = new HashMap<>();
for (int i = 1; i <= 11; i++) {
map.put(new MyKey(i), "value"+i);
}
for (int i = 1; i <=5; i++) {
map.remove(new MyKey(i));
}//table[1]下剩余6个结点
for (int i = 21; i <= 100; i++) {
map.put(new MyKey(i), "value"+i);//添加到扩容时，反树化
}
}
}、key-value中的key是否可以修改？
key-value存储到HashMap中会存储key的hash值，这样就不用在每次查找时重新计算每一个Entry或Node（TreeNode）的hash值了，因此如果已经put到Map中的key-value，再修改key的属性，而这个属性又参与hashcode值的计算，那么会导致匹配不上。
这个规则也同样适用于LinkedHashMap、HashSet、LinkedHashSet、Hashtable等所有散列存储结构的集合。